package tianhao.luo.search;

import java.util.ArrayList;
import java.util.List;

/**
 * 使用二分查找的前提是,该数组是有序的
 *
 * @author: tianhao.luo@hand-china.com 2021/6/19  16:10
 */
public class BinarySearch {
    private int[] array;

    public BinarySearch(int[] array) {
        this.array = array;
    }


    /**
     * 查找到一个符合的值就返回
     * @param value 要查找的值
     * @param left 左索引
     * @param right 右索引
     * @return 值的索引
     */
    public int search(int value,int left,int right){

        // 需要判断当前是否已经遍历完整个数组了
        // left>right表示未找到元素
        // 大于最大值或小于最小值也要退出循环
        if (left>right || value<array[0] || value>array[array.length-1]){
            return -1;
        }


        // 1.找到中间位置的元素
        int mid = (left+right)/2;

        // 2.判断是向左还是向右查找
        // 向右查找
        if (value>array[mid]){
            return search(value, mid+1, right);
        }else if (value<array[mid]){
            // 向左查找
            return search(value,left,mid-1);
        }else {
            // 匹配
            return mid;
        }
    }

    /**
     * 当一个有序数组{1,8, 10, 89, 1000, 1000，1234}中,
     * 有多个相同的数值时,如何将所有的数值都查找到,比如这里的1000
     *
     * 思路:
     * 1.在找到元素的时候,先不要立即返回
     * 2.向mid索引值的左边扫描,将找到的元素,加入到集合中
     * 3.向mid索引值的右边扫描,将找到的元素,加入到集合中
     */
    public List<Integer> searchTwo(int value, int left, int right){
        System.out.println("hello~");
        // 需要判断当前是否已经遍历完整个数组了
        // left>right表示未找到元素
        if (left>right || value<array[0] || value>array[array.length-1]){
            return new ArrayList<>();
        }


        // 1.找到中间位置的元素
        int mid = (left+right)/2;

        // 2.判断是向左还是向右查找
        // 向右查找
        if (value>array[mid]){
            return searchTwo(value, mid+1, right);
        }else if (value<array[mid]){
            // 向左查找
            return searchTwo(value,left,mid-1);
        }else {
            // 匹配
            List<Integer> list = new ArrayList<>();
            // 向左找相同元素
            int temp = mid -1;
            while (true){
                if (temp<0 || array[temp] != value){
                    break;
                }
                list.add(temp);
                temp--;
            }
            // 左边元素查找完毕后,将mid加入,可以保证集合中值是有序的
            list.add(mid);

            // 向右找相同元素
            temp = mid +1;
            while (true){
                if (temp>array.length-1 || array[temp] != value){
                    break;
                }
                list.add(temp);
                temp++;
            }
            return list;
        }
    }
}
